class Solution {
public:
    int trap(vector<int>& height) {
      int ans=0;
      int n=height.size();
      stack<int>st;
      for(int i=0;i<n;i++){
        while(!st.empty()&&height[st.top()]<height[i]){
            int cut=st.top();
            st.pop();
            if(st.empty()) break;
            int l=st.top();
            int r=i;
            int h=min(height[l],height[r])-height[cut];
            ans+=(r-l-1)*h;
        }
        st.push(i);
      }
      return ans;
    }
};
